

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2024-01-21
 * Time: 11:11
 */
public class A {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }

    }
    public TreeNode create(){
        TreeNode A=new TreeNode(3);
        TreeNode B=new TreeNode(5);
        TreeNode C=new TreeNode(1);
        TreeNode D=new TreeNode(6);
        TreeNode E=new TreeNode(2);
        TreeNode F=new TreeNode(0);
        TreeNode G=new TreeNode(8);
        TreeNode H=new TreeNode(7);
        TreeNode I=new TreeNode(4);
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.left=H;
        E.right=I;
        return A;

    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null){
            return null;
        }
        if(root==p||root==q){
            return root;
        }
        TreeNode node=lowestCommonAncestor(root.left,p,q);
        TreeNode node2=lowestCommonAncestor(root.right,p,q);
        if(node==null&&node2!=null){
            return node2;
        }

        if(node!=null&&node2==null){
            return node;
        }
        return root;
    }

}
